package dmsxl.shuzu;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/6 15:19
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 *
 * 注意：如果对空文本输入退格字符，文本继续为空。
 */
public class array2_r3_844 {

    public static void main(String[] args) {
//        String s = "ab#c", t = "ad#c";
        String s = "a##c", t = "#a#c";
        System.out.println(backspaceCompare(s, t));
    }

//    自己写的，过了，但是有点乱
    public static boolean backspaceCompare1(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();

        int c1 = 0;
        for (int i = 0; i < s1.length; i++){
            if (s1[i] != '#'){
                s1[c1] = s1[i];
                c1 += 1;
            }else if (s1[i] == '#' && c1 == 0){
                c1 = 0;
            } else c1 -= 1;
        }
        String s2 = String.valueOf(s1).substring(0,c1);

        int c2 = 0;
        for (int i = 0; i < t1.length; i++){
            if (t1[i] != '#'){
                t1[c2] = t1[i];
                c2 += 1;
            }else if (t1[i] == '#' && c2 == 0){
                c2 = 0;
            }else c2 -= 1;
        }
        String t2 = String.valueOf(t1).substring(0,c2);
        if (s2.compareTo(t2)==0) return true;
        return false;
    }

//    借助栈
    public static boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }

    public static String build(String str){
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; i++){
            char ch = str.charAt(i);
            if (ch != '#') ret.append(ch);
            else {
                if (ret.length() > 0) ret.deleteCharAt(ret.length() - 1);
            }
        }
        return ret.toString();
    }
}
